// hard

// 给定一个字符串s和一个字符模式串p
// 要求实现一个支持'?'和'*'的通配符匹配，两个字符串完全匹配才算匹配成功，如果匹配成功，返回true，否则返回false
// ? 可以匹配任何单个字符
// * 可以匹配任意字符串（包括空字符串） 
// 说明：s可能为空，且只包含从a-z的小写字母
//      p可能为空，且只包含从a-z的小写字母，以及字符'?'和'*'

// 解题思路1： 动态规划
// 1. 划分阶段，按照两个字符串的结尾位置进行阶段划分
// 2. 定义状态，dp[i][j]表示为：字符串s的前i个字符与字符串p的前j个字符是否匹配
// 3. 状态转移方程
//      1. 如果s[i-1] == p[j-1],或者p[j-1] == '?',则表示s的第i个字符与p的第j个字符是匹配的
//         s的第i个字符与p的第j个字符是否匹配取决于s的前i-1个字符与p的前j-1个字符是否匹配，
//          即dp[i][j] = dp[i-1][j-1]
//      2. 如果p[j-1] == '*',则p的第j个字符可以对应s中0-若干个字符
//          1. 如果当前*没有匹配当前第i个字符，则s的前i个字符与p的前j个字符是否匹配取决于s的前i-1个字符
//             与p的前j个字符是否匹配，即dp[i][j] = dp[i-1][j]
//          2. 如果当前*匹配了当前第i个字符，则s的前i个字符与p的前j个字符是否匹配取决于s的前i个字符与p的前
//              j-1个字符是否匹配，即dp[i][j] = dp[i][j-1]
//          3. 这两种情况只需匹配一种，就视为匹配，所以dp[i][j] = dp[i-1][j] or dp[i][j-1]
// 4. 初始条件
//      1. 默认状态下，两个空字符串是匹配的，即dp[0][0] = true
//      2. 当s为空空，p开始字符串为若干个*,两个字符串是匹配，即p[j-1] == '*',dp[0][j] = true
// 5. 最终结果
// dp[i][j]表示为：s的前i个字符与p的前j个字符是否匹配，则最终结果为dp[size_s][size_p],其中size_s是s的长度，size_p是p的长度

// 复杂度分析
// 时间复杂度：O(mn)
// 空间复杂度：O(mn)

function isMatch(s, p) {
    let size_s = s.length
    let size_p = p.length
    let dp = new Array(size_s + 1).fill(0).map(() => new Array(size_p + 1).fill(false))
    dp[0][0] = true

    for (let j = 1; j < size_p + 1; j++) {
        if (p[j - 1] !== '*') {
            break
        }
        dp[0][j] = true
    }

    for (let i = 1; i < size_s + 1; i++) {
        for (let j = 1; j < size_p + 1; j++) {
            if (s[i - 1] === p[j - 1] || p[j - 1] === '?') {
                dp[i][j] = dp[i - 1][j - 1]
            } else if (p[j - 1] === '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1]
            }
        }
    }
    return dp[size_s][size_p]
}

s = "adceb"
p = "*a*b"
console.log(isMatch(s, p))